题解：P10903 [蓝桥杯 2024 省 C] 商品库存管理

cnblogs食用也行

题目大意

有一个初始化为 的 长度为 的序列，现有 个操作，每次将区间 中的数量加 ，求如果不做某个操作将会有多少个数量为 的量。

解题思路

通过将区间内所有数量增加这句话我们就能很直接的想到差分。

这题我们可以使用差分先处理将所有的操作执行后的数组，然后在算出如果减去某个操作的数组是什么样子。

不难想，减去某个操作后数组中 的个数就是区间外本来就是 的量的个数和区间内被变成 的量的个数相加。

这部分代码可以使用前缀和优化。

求解公式为：

代码

#include <bits/stdc++.h>
using namespace std;

int n, m;
int l[300005], r[300005];
int a[300005], b[300005], c[300005];

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> l[i] >> r[i];
		a[l[i]]++;
		a[r[i] + 1]--;
	}
	
	for (int i = 1; i <= n; i++)
	{
		a[i] += a[i - 1]; // 前缀和
		if (a[i] == 0)
			b[i]++; // 统计为 0
		if (a[i] == 1)
			c[i]++; // 统计为 1
		b[i] += b[i - 1]; // 前缀和
		c[i] += c[i - 1]; // 前缀和
	}
	
	for (int i = 1; i <= m; i++)
	{
		cout << b[l[i] - 1] + b[n] - b[r[i]] + c[r[i]] - c[l[i] - 1] << "\n";
		// 区间外（1~l[i]-1, r[i]+1 ~ n） 为 0 的数 + 区间内为 1 的数。 
	}
	return 0; 
}

// 记录：https://www.luogu.com.cn/record/174366827